//加油站  力扣134
//贪心    
//定义数组diff=gas-cost，若diff总和>=0则能绕一圈，若<0则不能
class Solution {
public:
	int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
		vector<int> diff(gas.size());
		for(int i = 0; i < diff.size(); i++)
			diff[i] = gas[i] - cost[i];
		
		int sum = 0;
		for(int i = 0; i < diff.size(); i++)
			sum += diff[i];
		if(sum < 0) return -1;
		
		int cursum = 0;
		int presum = 0;
		int startpos = 0;
		for(int i = 0; i < diff.size(); i++)
		{
			cursum += diff[i];
			if(cursum < 0) 
			{
				cursum = 0;
				startpos = i + 1;
			}
		}
		return startpos;
	}
};
